package edu.kit.csl.cratylus.extraction;

/**
 * This utility class provides functions for calculating the Levenshtein 
 * distance. The implementation is taken from Wikipedia.
 */
public final class LevenshteinUtils {

	/*
	 * Private constructor for utility classes. 
	 */
	private LevenshteinUtils() {
		;
	}
	
	/**
	 * Calculates the Levenshtein distance matrix between two strings. The 
	 * implementation is similar to the reference in <a 
	 * href="http://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance#Java">
	 * Wikibooks</a> and runs in O(n*m) with space complexity O(n*m), where
	 * n and m are the lengths of the strings to compare.
	 * 
	 * @param str1 the first string
	 * @param str2 the second string to compare with the {@code str1}
	 * @return the Levenshtein distance matrix nxm between {@code str1} 
	 * 		and {@code str2}
	 * @throws NullPointerException if one of the arguments or their content
	 * 				is null
	 */
	public static int[][] distanceMatrix(String[] str1, String[] str2) {
		int[][] distance = new int[str1.length + 1][str2.length + 1];
		for (int i = 0; i <= str1.length; i++) {
			distance[i][0] = i;
		}
		for (int j = 1; j <= str2.length; j++) {
			distance[0][j] = j;
		}

		for (int i = 1; i <= str1.length; i++) {
			for (int j = 1; j <= str2.length; j++) {
				distance[i][j] = minimum(distance[i - 1][j] + 1,
						distance[i][j - 1] + 1, distance[i - 1][j - 1]
								+ ((str1[i - 1].equals(str2[j - 1])) ? 0 : 1));
			}
		}
		return distance;
	}

	/**
	 * Calculates the Levenshtein distance between two strings, using their
	 * distance matrix and dynamic programming.
	 * 
	 * @param str1 the first string
	 * @param str2 the second string to compare with the {@code str1}
	 * @return the Levenshtein distance between {@code str1} and {@code str2}
	 * @throws NullPointerException if one of the arguments or their content
	 * 				is null
	 * @see #distanceMatrix(String[], String[])
	 */
	public static int distance(String[] str1, String[] str2) {
		int[][] matrix = distanceMatrix(str1, str2); 
		return matrix[str1.length][str2.length];
	}
	
	/* (non-Javadoc)
	 * Minimum of a, b, c.
	 */
	private static int minimum(int a, int b, int c) {
		return Math.min(Math.min(a, b), c);
	}
}
